package leetcode.top100;

import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/**
 * 给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
 *
 * 说明：解集不能包含重复的子集。
 *
 * 示例:
 *
 * 输入: nums = [1,2,3]
 * 输出:
 * [
 *   [3],
 *   [1],
 *   [2],
 *   [1,2,3],
 *   [1,3],
 *   [2,3],
 *   [1,2],
 *   []
 * ]
 *
 * @date 2020/4/5 21:05
 */
public class Code78_SubArr {
    public static void main(String[] args) {
        int[]arr = {1,2,3};
        for (List<Integer> list : new Code78_SubArr().subsets(arr)) {
            System.out.println(list);
        }
    }
    public List<List<Integer>> subsets(int[] nums) {
        if(nums == null || nums.length == 0) return new LinkedList<>();
        List<List<Integer>> res = new LinkedList<>();
        process2(nums,0,res,new Stack<Integer>());
        return res;
    }

    private void process1(int[] nums, int i, List<List<Integer>> res, Stack<Integer> stack) {
        if(i == nums.length){
            res.add(new LinkedList<>(stack));
            return;
        }
        //当前要或不要
        stack.push(nums[i]);
        process1(nums,i+1,res,stack);
        stack.pop();
        process1(nums,i+1,res,stack);
    }
    private void process2(int[] nums, int index, List<List<Integer>> res, Stack<Integer> stack) {
        res.add(new LinkedList<>(stack));
        if(index == nums.length){
            return;
        }
        //从当前位置往后遍历
        for (int i = index; i < nums.length; i++) {
            stack.push(nums[i]);
            process2(nums,i+1,res,stack);
            stack.pop();
        }
    }
}
